package nc.hw;

import java.util.*;

public class HJ28 {
    private static int numsOfPrimeCoup(int[] nums) {
        List<Integer> odds = new ArrayList<>();
        List<Integer> evens = new ArrayList<>();
        for (int num : nums) {
            if (num % 2 == 0) {
                evens.add(num);
            } else {
                odds.add(num);
            }
        }
        int[] evenMatchs = new int[evens.size()];
        int max = 0;
        for (int i = 0; i < odds.size(); i++) {
            Integer odd = odds.get(i);
            int[] used = new int[evens.size()];
            if (find(odd, evens, used, evenMatchs)) {
                max += 1;
            }
        }
        return max;
    }

    private static boolean find(int odd, List<Integer> evens, int[] used, int[] evenMatchs) {
        for (int i1 = 0; i1 < evens.size(); i1++) {
            Integer even = evens.get(i1);
            // 如果even使用过，跳过
            if (isPrime(odd + even) && used[i1] == 0) {
                // 偶数没有用过,那么进行匹配
                // 如果该偶数从来都没有匹配任何值，那么就用，或者匹配的值存在另外的匹配，也可用
                used[i1] = 1;
                if (evenMatchs[i1] == 0 || find(evenMatchs[i1], evens, used, evenMatchs)) {
                    evenMatchs[i1] = odd;
                    return true;
                }
            }
        }
        return false;
    }

    private static boolean isPrime(int num) {
        if (num == 1) {
            return false;
        }
        for (int i = 2; i * i <= num; i++) {
            if (num % i == 0) {
                return false;
            }
        }
        return true;
    }

    public static void main(String[] args) {
        String sss = "20923 22855 2817 1447 29277 19736 20227 22422 24712 27054 27050 18272 5477 27174 13880 15730 7982 11464 27483 19563 5998 16163";
        String[] s = sss.split(" ");
        int[] nums = new int[s.length];
        Arrays.sort(nums);
        for (int i = 0; i < s.length; i++) {
            nums[i] = Integer.parseInt(s[i]);
        }
        System.out.println(numsOfPrimeCoup(nums));
    }

}
